package likou

import "math"

func NearestExit(maze [][]string, entrance []int) int {
	// 使用深度优先算法解题
	// 获取起点坐标
	i, j := entrance[0], entrance[1]
	minSteps := math.MaxInt32
	// 定义移动动作
	dirs := [][]int {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	var dfs func(int, int, int)

	dfs = func(steps, x, y int) {
		if (x == 0 || x == len(maze) - 1 ||
			y == 0 || y == len(maze[0]) - 1) &&
			(x != i || y != j) {
			minSteps = int(math.Min(float64(minSteps), float64(steps)))
		}

		for _, dir := range dirs {
			nextX := dir[0] + x
			nextY := dir[1] + y
			if nextX < 0 || nextX > len(maze) - 1 ||
				nextY < 0 || nextY > len(maze[0]) - 1 ||
				maze[nextX][nextY] == string('+') {
				continue
			}
			maze[nextX][nextY] = string('+')
			dfs(steps + 1, nextX, nextY)
			// 回溯，去掉修改
			maze[nextX][nextY] = string('.')
		}
	}

	dfs(0, i, j)
	if minSteps != math.MaxInt32 {
		return minSteps
	} else {
		return -1
	}
}
